This invention relates to a method of performing a modular inversion, especially, though not exclusively, in the context of generating so-called RSA(trademark) public and private key pairs.
In the RSA(trademark) cryptographic scheme, an RSA key pair consists of an RSA public key and an RSA private key. Further information regarding the RSA scheme can be found in an article entitled xe2x80x9cA Method of Obtaining Digital Signatures and Public Key Cryptosystemsxe2x80x9d by R. L. Rivest, A. Shamir and L. Adleman, published in Communications of the ACM, Vol 21 (1978), pages 120-126. The public and private keys are generated by some agent and then typically assigned to a particular user. The user makes use of the private key for generating digital signatures and for decrypting messages, and distributes the public key so that other users may verify the signatures generated or encrypt messages to be sent to the user in question. Often, the private key resides on a smart card because this class of device offers both secure storage and secure usage of the key.
It is also becoming increasingly common, because of needs for higher levels of security in some contexts, that there are requirements for RSA keys used by smart cards to be generated by the card itself. In this case, the private key data is never, at any stage, available off the card. It is only recently that smart cards have reached the levels of computational capability necessary to make this key pair generation feasible within an acceptable time.
A valid RSA public key, consists of the following data:
a modulus n, which is a non-negative integer equal to the product of two odd primes p and q; and
a public exponent e, which is a non-negative integer between 3 and nxe2x88x921 inclusive, and whose greatest common divisor with l(n) is 1. Here l(n) is the least common multiple of both pxe2x88x921 and qxe2x88x921.
A valid RSA private key, in one of the two common representations, consists of the following data:
a modulus n, equal to that in the corresponding RSA public key; and
a private exponent d, which is a positive integer less than n satisfying e d=1 mod l(n). By xe2x80x9cmodxe2x80x9d is meant modular reduction, i.e. the remainder when e d is divided by l(n) is equal to 1.
The public key is typically used to encrypt data, while the corresponding private key may be used to decrypt data so encrypted. Alternatively, the private key may be used to sign data. The corresponding public key may then be used to validate the signature so computed.
Typically in RSA key pair generation, the public exponent e is specified to be some predefined value. It is advantageous that this value be prime (so that the condition that the greatest common divisor of e and l(n)=1 is more likely to hold), and that its binary representation consist of as few non-zero digits as possible (so that exponentiation computations using it are fast). Typical values used in practice are 3, 17, 257 and 65537. This is a very small value in relation to the typical size of the modulus (200-300 digits) required for reasonable levels of security.
During key generation therefore, having computed the modulus by whatever means are appropriate, the problem is then, given the value e, to compute the corresponding private exponent d. Since e d=1 mod l(n), it is required to compute d=exe2x88x921 mod l(n). This so-called modular inversion is the operation with which the present invention is concerned. The method is one which should be suitable for implementation on memory constrained devices, such as smart cards, under the typical constraints on the value of e noted above.
It should be noted that the other common representation of the RSA private key data is in the so-called Chinese Remainder Theorem form. In this form, the factors p and q of the modulus are stored, as well as the values dp=d mod pxe2x88x921 and dq=d mod qxe2x88x921. The purpose of storing the key data in this form is that operations using the private key can then typically be performed much more quickly. The two values dp and dq represent the private exponent d. Their relation to the public exponent e is given by: dp=exe2x88x921 mod pxe2x88x921 and dq=exe2x88x921 mod qxe2x88x921. In other words, two modular inversions are required in this case. Hence, the method of the present invention is also relevant, i.e. an efficient computation of the modular inverse is required.
To summarize, the object of the present invention is to provide an efficient method for modular inversion. This is of specific use in the context of RSA key generation in smart cards. Also, it may be of use in other applications requiring modular inversion operations with values of input parameters restricted as is typical for RSA.
There are a number of methods available for modular inversion. In particular, the most commonly used are, or are variants of, the following two methods:
the extended Euclidean algorithm,
the binary extended GCD algorithm
(see algorithms 2.107 and 14.61 in the book xe2x80x9cHandbook of Applied Cryptographyxe2x80x9d by A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, CRC Press, 1996, and algorithm X in section 4.5.2 of xe2x80x9cThe Art of Computer Programming. Volume 2 Seminumerical Algorithmsxe2x80x9d by D. Knuth, Addison Wesley, 1981). It should be noted that variants such as Lehmer""s algorithm (algorithm L in section 4.5.2 of xe2x80x9cThe Art of Computer Programming. Volume 2 Seminumerical Algorithmsxe2x80x9d by D. Knuth, Addison Wesley, 1981) are not considered here since they are complex (large code size) algorithms unsuitable for the smart card applications.
The drawbacks of these methods are similar in that both have sizeable requirements in terms of RAM usage for temporary variables, together with significant requirements in terms of code size. In the context of smart card applications, these issues are of great significance. Another drawback of the known methods is that it is common, in practice, that cryptographic coprocessors available on smart card platforms are restricted to support modular arithmetic operations with only odd values for the modulus, since use is made of Montgomery arithmetic. In this case direct application of the conventional inversion techniques to the original problem with hardware support for the relevant arithmetic operations may prove problematic, since e.g. l(n) is even.
The present invention therefore seeks to provide a method of performing a modular inversion, which overcomes, or at least reduces, the above-mentioned problems of the prior art.
Accordingly, in a first aspect, the invention provides a method of determining a modular inverse exe2x88x921 mod m of a data value e, the method comprising the steps of:
(i) determining the value of the data value e;
(ii) determining a value of m for the inversion;
(iii) calculating the value of m mod e by determining a remainder value r of m divided by e;
(iv) determining an inverse t=rxe2x88x921 mod e; and
(v) determining the modular inverse exe2x88x921 mod m utilising at least the value t.
In preferred embodiments, the step (iv) of determining an inverse t=axe2x88x921 mod e, is performed either by computing aexe2x88x922 mod e if e is prime or by using the extended Euclidean or binary extended GCD algorithms for more general values of e.
Preferably, the method is utilized in an RSA(trademark) cryptographic system to generate a private exponent d used to determine an RSA(trademark) private key for the cryptographic system. The method is preferably carried out by a processor on a smartcard.